class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    /*
    dp[i][j]表示以str1[i]str2[j]结尾的公共子串的长度
    递推式
    如果str1[i]==str2[j],则dp[i][j]=dp[i-1][j-1]+1;
    如果str1[i]!=str2[j]，则不能构成公共子串,dp[i][j]=0
    */
    string LCS(string str1, string str2) {
        // write code here
        int size1=str1.size();
        int size2=str2.size();
        vector<vector<int> >dp(size1+1,vector<int>(size2+1,0));
        int max=0;
        int flag=0;
        for(int i=1;i<=size1;i++)
        {
            for(int j=1;j<=size2;j++)
            {
                if(str1[i-1]==str2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=0;
                if(dp[i][j]>max)
                { 
                 max=dp[i][j];
                 flag=i;
                }
            }
            
        }
        return str1.substr(flag-max,max);
    }
};